#ifndef DATABASE_SKIPLIST_H
#define DATABASE_SKIPLIST_H

#include "../Alloc.hpp"
#include "../../base/Defind.hpp"
#include "../Malloc.hpp"

#include <memory>
#include <iostream>
#include <random>

namespace DBServer
{
namespace Database
{
template<class T>
class SkiplistNode;

template<class T>
class SkiplistLevel {
public:
    SkiplistNode<T> *forward;
    int span;
};

template<class T>
class SkiplistNode {
public:
    T *data;
    SkiplistLevel<T> *level;
    SkiplistNode *backward;
    double score;             
};

template<class T>
class Return {
public:
    T data;
    double score;
};

template<typename T>
class Skiplist {
public:
    Skiplist();
    ~Skiplist();

    int size();

    void insert(const T&, double);
    void erase(const T&, double);
    std::shared_ptr<Return<T>> get_score_first_in_range(double, double);
    std::shared_ptr<Return<T>> get_score_last_in_range(double, double);
    int get_location(const T&, double);
    std::shared_ptr<Return<T>> get_element_by_rank(int);
    bool is_in_range(double, double);
    int erase_range_by_score(double, double);
    int erase_range_by_rank(int, int);

    Skiplist(const Skiplist&&) = delete;
    Skiplist(const Skiplist&) = delete;
    Skiplist& operator=(const Skiplist&) = delete;
    Skiplist&& operator=(const Skiplist&&) = delete;

    /* test */
    void print();
private:
    SkiplistNode<T>* node_create(int, double, const T&);
    void node_release(SkiplistNode<T>*);
    int random_level();

private:
    int max_level;
    int node_num;
    SkiplistNode<T> *head, *tail;
};

template<typename T>
int Skiplist<T>::size() { return node_num; }

template<typename T>
SkiplistNode<T>*
Skiplist<T>::node_create(int level, double score, const T& data)
{
    SkiplistNode<T> *node = New<SkiplistNode<T>>();
    node->level = (SkiplistLevel<T>*)Alloc::GetInstance()->New((sizeof(SkiplistNode<T>*) + sizeof(int)) * level);
    for (int i = 0; i < level; ++i)
    {
        node->level[i].span = 0;
        node->level[i].forward = nullptr;
    }
    node->score = score;
    node->data = New<T>(data);   // copy the data
    return node;
}

template<typename T>
void
Skiplist<T>::node_release(SkiplistNode<T>* node)
{
    Delete(node->data);
    Alloc::GetInstance()->Delete((char*)node->level);
    Delete(head->backward);
}

template<typename T>
int
Skiplist<T>::random_level() 
{
    static const int threshold = 0x7fff * SKIPLIST_P;
    static std::default_random_engine e;
    static std::uniform_real_distribution<double> u(1, 0x7fff);
    e.seed(time(0));
    int level = 1;
    while (u(e) < threshold)
            ++level;
    return (level<SKIPLIST_MEX_LEVEL) ? level : SKIPLIST_MEX_LEVEL;
}

template<typename T>
Skiplist<T>::Skiplist()
    : max_level(0), node_num(0)
{
    head = tail = nullptr;
}

template<typename T>
Skiplist<T>::~Skiplist() {
    while (head != tail)
    {
        head = head->level[0].forward;
        node_release(head->backward);
    }
    Delete(tail);
}

template<typename T>
void
Skiplist<T>::insert(const T& data, double score) {
    // updata -> record the nodes that need to be updated at each layer
    // rank -> reacord thea distance that the nodes to be update and the node to be inserted
    // iter -> iterator for traversing the skip list
    SkiplistNode<T> *iter;
    SkiplistNode<T> *updata[SKIPLIST_MEX_LEVEL];
    int rank[SKIPLIST_MEX_LEVEL];

    // if skip list is empty
    if (node_num == 0) goto create;

    // traverse the skip list to find location for insrerting
    iter = head;
    for (int i = max_level-1; i >= 0; --i) 
    {
        rank[i] = (i == max_level) ? 0 : rank[i+1];
        while (iter->level[i].forward &&
                (iter->level[i].forward->score < score || 
                (iter->level[i].forward->score == score &&
                *(iter->level[i].forward->data) != data)))
        {
            rank[i] += iter->level[i].span;
            iter = iter->level[i].forward;
        }
        updata[i] = iter;
    }

    // adjust the height of skip list
    // the number of layers of new nodes is generated by randomization algorithn
create:
    int level = random_level();
    if (node_num == 0)
    { 
        max_level = level;
        goto insert;
    }
    // if the height of the new nodes is greater than overall height of the original
    // skip list, the height of the skip list needs to be adjusted
    if (level > max_level)
    {
        for (int i = max_level-1; i < level; ++i)
        {
            rank[i] = 0;
            updata[i] = head;
            updata[i]->level[i].span = node_num;
        }
        max_level = level;
    }
    
    // insert the new node into the skip list
insert:
    iter = node_create(level, score, data);
    if (node_num == 0) // skip list is nullptr
        head = iter;
    else
    {
        for (int i = max_level-1; i >= 0; --i)
        {
            // set attribute of new node
            iter->level[i].forward = updata[i]->level[i].forward;
            iter->level[i].span = updata[i]->level[i].span - (rank[0] - rank[i]);
            // update original node attribute
            updata[i]->level[i].forward = iter;
            updata[i]->level[i].span = rank[0] - rank[i] + 1;
        }
    }

    // when the height of the new node is less than the height of the original node
    if (level < max_level) 
        for (int i = level; i < max_level; ++i)
         updata[i]->level[i].span++;

    // adjust backward pointer
    iter->backward = (node_num == 0) ? nullptr : updata[0];
    if (iter->level[0].forward)
        iter->level[0].forward->backward = iter;
    else
        tail = iter;

    // add len 
    ++node_num;
}

template<typename T>
void
Skiplist<T>::erase(const T& data, double score) {
    // determine whether there is
    if (score < head->score || score > tail->score) return;

    SkiplistNode<T> *update[SKIPLIST_MEX_LEVEL], *iter;
    SkiplistNode<T> *tmp;   // point to the node which need to be deleted
    iter = head;
    for (int i = max_level-1; i >= 0; --i)
    {
        while (iter->level[i].forward && 
                (iter->level[i].forward->score < score ||
                 (iter->level[i].forward->score == score &&
                    *(iter->level[i].forward->data) != data)))
        {
            iter = iter->level[i].forward;
            update[i] = iter;
        }
    }
    
    // if the node which need to delete is the head node
    if (iter == head && *(iter->data) == data && iter->score == score)
    {
        head = iter->level[0].forward;
        if (iter == tail)
            tail = nullptr;
            tmp = iter;
        goto finish;
    }

    // the iter is not move and the update is not update
    if (head == iter)
        for (int i = max_level-1; i >= 0; --i)
            update[i] = head;

    if (iter->level[0].forward->score != score || *(iter->level[0].forward->data) != data)
        return;
    
    tmp = iter->level[0].forward;
    for (int i = max_level-1; i >= 0; --i)
    {
        if (update[i] == iter) 
        {
            update[i]->level[i].forward = iter->level[i].forward->level[i].forward;
            update[i]->level[i].span += iter->level[i].span - 1;
        }
        else update[i]->level[i].span -= 1;
    }
    if (tmp == tail) 
        tail = tmp->backward;
finish:
    // number of nodes minus one
    node_num -= 1;

    // release node
    node_release(tmp);
}

template<typename T>
std::shared_ptr<Return<T>>
Skiplist<T>::get_score_first_in_range(double min, double max) {
    if (max < head->score || min > tail->score) return nullptr;

    SkiplistNode<T> *iter;
    iter = head;

    for (int i = max_level-1; i >= 0; --i)
    {
        while (iter->level[i].forward &&
                iter->level[i].forward->score < min)
            iter = iter->level[i].forward;
    }

    if (iter->level[0].forward->score > max) return nullptr;
    iter = iter->level[0].forward;
    std::shared_ptr<Return<T>> t = std::make_shared<Return<T>>();
    t->data = *(iter->data);
    t->score = iter->score;
    return t;
}

template<typename T>
std::shared_ptr<Return<T>>
Skiplist<T>::get_score_last_in_range(double min, double max) {
    if (max < head->score || min > tail->score) return nullptr;

    SkiplistNode<T> *iter;
    iter = head;

    for (int i = max_level-1; i >= 0; --i)
    {
        while (iter->level[i].forward &&
                iter->level[i].forward->score < max)
            iter = iter->level[i].forward;
    }

    if (iter->score < min) return nullptr;
    std::shared_ptr<Return<T>> t = std::make_shared<Return<T>>();
    t->data = *(iter->data);
    t->score = iter->score;
    return t;
}

template<typename T>
int
Skiplist<T>::get_location(const T& t, double score) {
    int rank = 1;
    SkiplistNode<T> *iter;
    iter = head;
    for (int i = max_level-1; i >= 0; --i)
    {
        while (iter->level[i].forward &&
                (iter->level[i].forward->score < score ||
                (iter->level[i].forward->score == score && 
                    *(iter->level[i].forward->data) != t)))
        {
            rank += iter->level[i].span;
            iter = iter->level[i].forward;
        }
    }

    if (iter->level[0].forward->score != score || *(iter->level[0].forward->data) != t) return -1;
    return rank+1;
}

template<typename T>
std::shared_ptr<Return<T>>
Skiplist<T>::get_element_by_rank(int rank) {
    if (rank > node_num) return nullptr;

    SkiplistNode<T> *iter;
    iter = head;

    for (int i = max_level-1; i >= 0; --i)
    {
        while (iter->level[i].forward && iter->level[i].span < rank)
        {
            rank -= iter->level[i].span;
            iter = iter->level[i].forward;
        }
    }
    std::shared_ptr<Return<T>> t = std::make_shared<Return<T>>();
    t->data = *(iter->data);
    t->score = iter->score;
    return t;
}

template<typename T>
bool
Skiplist<T>::is_in_range(double min, double max) {
    if (head->score > max || tail->score < min) return false;

    SkiplistNode<T> *iter;
    iter = head;

    for (int i = max_level-1; i >= 0; --i)
        while (iter->level[i].forward && iter->level[i].forward->score < min)
            iter = iter->level[i].forward;

    if (iter->level[0].forward && 
        iter->level[0].forward->score > min && 
        iter->level[0].forward->score < max)
        return true;
    return false;
}

template<typename T>
int
Skiplist<T>::erase_range_by_score(double min, double max) {
    SkiplistNode<T> *begin, *end;
    begin = head;
    end = head;
    
    for (int i = max_level-1; i >= 0; --i)
    {
        while (begin->level[i].forward &&
                begin->level[i].forward->score < min)
            begin = begin->level[i].forward;

        while (end->level[i].forward &&
                end->level[i].forward->score < max)
            end = end->level[i].forward;
    }

    int counter = 0;
    while (begin != end)
    {
        auto tmp = begin;
        begin = begin->level[0].forward;
        erase(*(tmp->data), tmp->score);
        ++counter;
    }
    // delete end 
    erase(*(end->data), end->score);
    return counter+1;
}

template<typename T>
int
Skiplist<T>::erase_range_by_rank(int first, int last) {
    SkiplistNode<T> *iter;
    iter = head;
    int temp = first;
    for (int i = max_level-1; i >= 0; --i)
    {
        while (iter->level[i].forward &&
                temp > 0 &&
                iter->level[i].span < temp)
        {
            temp -= iter->level[i].span;
            iter = iter->level[i].forward;
        }
    }
    int counter = 0;
    while (first != last && iter) 
    {
        auto tmp = iter;
        iter = iter->level[0].forward;
        ++first;
        ++counter;
        erase(*(tmp->data), tmp->score);
    }
    return counter;
}

template<typename T>
void
Skiplist<T>::print() {
    SkiplistNode<T> *iter = head;
    while (iter)
    {
        std::cout << "score : " << iter->score << std::endl;
        std::cout << "data : " << *iter->data << std::endl << std::endl;
        iter = iter->level[0].forward;
    }
}

} // namespace Database
} // namespace DBServer



#endif 